#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class Solution:
    # 错误
    def isValidBST(self, root):
        if root is None:
            return True

        is_valid, _, _ = self.rec_is_valid_bst(root)
        return is_valid

    def rec_is_valid_bst(self, node):
        # if node is None:
        #     return True
        assert node is not None

        # NOTE: 这里不要也可以: 只不过是为了更早的结束判定
        if not self.check_cur_node(node):
            return False, -1, -1

        print(node.val)

        val = node.val
        min, max = val, val
        if node.left:
            print('left ===== %s' % node.left.val)
            is_left, max_left, min_left = self.rec_is_valid_bst(node.left)
            if not (is_left and val > max_left):
                return False, -1, -1        # 既然false, min, max无所谓了
            min = min_left
        if node.right:
            print('right ===== %s' % node.right.val)
            is_right, max_right, min_right = self.rec_is_valid_bst(node.right)
            if not (is_right and val < min_right):
                return False, -1, -1        # 既然false, min, max无所谓了
            max = max_right
        return True, max, min

    def check_cur_node(self, node):
        left, right = node.left, node.right
        if left and node.val <= left.val:
            return False
        if right and node.val >= right.val:
            return False

        return True


def main():
    print("start main")

    root = TreeNode(1)
    left = TreeNode(1)
    root.left = left
    s = Solution()
    ret = s.isValidBST(root)
    print(ret)

if __name__ == "__main__":
    main()
